#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <stdbool.h>


typedef int ElemType;
typedef struct {
    ElemType *elem;//存储严肃的起始地址
    int TableLen;//元素个数
}SSTable;

void ST_Init(SSTable& ST, int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
    int i;
    srand((unsigned int)time(NULL));
    for(i=0;i<ST.TableLen;i++) {
        ST.elem[i] = rand() % 100;//生成的是0~99之间的随机数
    }
}
//打印数组中的元素
void ST_Print(SSTable ST)
{
    for(int i=0;i<ST.TableLen;i++)
    {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}

//快排的核心函数
//挖坑法
int parition(ElemType *A, int low, int high)
{
    ElemType pivot=A[low];//拿最左边的作为分割值，并存储下来
    while(low<high)
    {
        while (low<high&&A[high]>=pivot)
        {
            high--;
        }

        A[low]=A[high];
        while(low<high&&A[low]<=pivot)
        {
            low++;
        }

        A[high]=A[low];
    }
    A[low]=pivot;
    return low;//把分割值放到中间位置
}

void QuickSort(ElemType *A, int low, int high)
{
    if(low<high)
    {
        int pivot_pos= parition(A,low,high);//pivot用来存分割值的位置
        QuickSort(A,low,pivot_pos-1);//前一半继续递归排好
        QuickSort(A,pivot_pos+1,high);
    }
}

int main()
{
    SSTable ST;
    ST_Init(ST,10);
    ElemType A[10]={64,94,95,79,69,84,18,22,12,78};
    memcpy(ST.elem,A,sizeof(A));
    ST_Print(ST);
    QuickSort(ST.elem,0,9);//注意这个位置是n-1,也就是9，因为函数取了high位置的值
    ST_Print(ST);
    return 0;
}